package madixin.t337;

import java.util.HashMap;
import java.util.Map;

class Solution {

    private Map<TreeNode, Integer> index = new HashMap<>();

    public int rob(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (index.get(root) != null) {
            return index.get(root);
        }

        //统计抢自己和孙子
        int robCur = root.val;
        if (root.left != null) {
            robCur += rob(root.left.left);
            robCur += rob(root.left.right);
        }

        if (root.right != null) {
            robCur += rob(root.right.left);
            robCur += rob(root.right.right);
        }

        //因为不能抢两个直接相连的房子。
        //所以要么抢自己和孙子，要么抢2个儿子
        robCur = Math.max(robCur, (rob(root.left) + rob(root.right)));
        index.put(root, robCur);
        return robCur;
    }
}